/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */

// 四数之和相当于三数之和外面再来一层循环。相当于k和i控制前两个下标的位置。然后控制去重和修建即可。
var fourSum = function (nums, target) {
  let arr = [];
  nums.sort((a, b) => a - b);
  for (let k = 0; k < nums.length; k++) {
    if (nums[k] > target && k > 0 && target > 0) break;
    if (k > 0 && nums[k] === nums[k - 1]) continue;
    for (let i = k + 1; i < nums.length; i++) {
      if (i > k + 1 && target > 0 && nums[i] + nums[k] > target) break;
      if (i > k + 1 && nums[i] == nums[i - 1]) continue;
      let left = i + 1;
      let right = nums.length - 1;
      while (left < right) {
        let sum = nums[k] + nums[i] + nums[left] + nums[right];
        if (sum === target) {
          arr.push([nums[k], nums[i], nums[left], nums[right]]);
          while (left < right && nums[right] === nums[right - 1]) right--;
          while (left < right && nums[left] === nums[left + 1]) left++;
          left++;
          right--;
        } else if (sum > target) {
          right--;
        } else {
          left++;
        }
      }
    }
  }
  return arr;
};
